// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

const LL mask = (1LL<<40) - 1;

const LL v1[] = {1611516670,0,10504600733,250614,24831098818,502983,47910667784,748963,85091177611,995306,144987890395,1248487,241479741103,1498258,396925287501,1747444,647343511917,1998844,1050759939994,2248777,6995323118,2500400,19177755253,2753611,38803296781,3001393,70419469617,3250603,121352198450,3500189,203403333351,3748878,335585309480,3999081,548526603120,4250961,891568792743,4500820,4011330338,4752339,14370630249,5004364,31059159172,5255599,57943890614,5512697,101254405922,5761815,171026377942,6011435,283426982212,6261011,464501064994,6511001,756206110651,6761575,1473880836,7012600,10282873289,7255844,24473902285,7500029,47335234538,7749066,84164171463,8002855,143494510838,8250170,239073950242,8499688,393049629374,8749837,641099940086,9000463,1040701728550,9249823,6806229870,9504060,18873131527,9756980,38312556854,10006016,69628901907,10254941,120078616969,10504170,201351630935,10753859,332280076921,11005541,543201970236,11256920,882990965157,11505757,3851233418,11754789,14112718818,12003250,30643671327,12253837,57274551969,12506329,100176120869,12755285,169289292334,13006129,280628588160,13255884,459992934005,13506761,748943643585,13755217,1337854506,14003713,10063739019,14252978,24120883462,14508693,46766531567,14760977,83248007737,15011683,142018597712,15263006,236696297515,15514848,389219300036,15765017,634929391393,16015235,1030761155188,16265370,6620357676,16516066,18573696825,16764613,37830176352,17013804,68851800982,17265772,118826730177,17517443,199334877911,17768048,329031146994,18017773,537968039366,18267828,874559255859,18516743,3691881458,18767639,13856007495,19017244,30230116928,19266808,56608327843,19515097,99102853322,19762991,167560289742,20012407,277843215574,20262671,455505780300,20513725,741714970433,20764119,1202088386,21014793,9845023648,21268022,23768539351,21521369,46198915518,21776537,82333594782,22028492,140545505090,22278152,234323188514,22530433,385396290797,22779772,628770636033,23031470,1020839580415,23281883,6435063656,23537550,18275193662,23783926,37349296386,24032362,68077117476,24280309,117578737596,24530608,197324398366,24780011,325792323073,25031296,532750388397,25282091,866153773131,25533395,3535227868,25785064,13603643125,26034534,29823565243,26290106,55953385061,26540391,98047759730,26788236,165860564948,27038504,275105008668,27289501,451094609069,27539195,734608702871,27789597,1069184517,28039980,9630919399,28288783,23423623727,28541830,45643266564,28791285,81438460553,29040198,139103470162,29289505,232000112395,29539710,381653883227,29790824,622741727028,30040231,1011127184687,30290504,6253085456,30539972,17982032071,30791086,36877021659,31037671,67316296707,31287094,116353077724,31539440,195349896300,31787638,322611458168,32037695,527626108416,32287610,857898708083,32538480,3380405496,32786560,13354228762,33040919,29421766079,33294427,55306098243,33543018,97004999528,33793327,164180708576,34042893,272398809312,34293534,446735001036,34544671,727585502349,34795503,937685173,35042602,9419077867,35294469,23082353134,35544907,45093489533,35792169,80552785887,36038770,137676674080,36289038,229701585730,36539205,377951024021,36790658,616776528825,37041078,1001517425426,37291298,6072677726,37541449,17691400485,37792864,36408822720,38036708,66562041892,38286741,115137995242,38537905,193392433859,38789864,319458043535,39039571,522546049723,39289923,849714882133,39539377,3227401830,39789970,13107744445,40042828,29024687081,40295186,54666415645,40547257,95974489732,40796650,162520587621,41043465,269724402982,41294998,442426611046,41545883,720644811724,41796761,807311470,42047577,9209049679,42293658,22744003927,42546233,44548418983,42798098,79674693251,43049621,136262092829,43301657,227422736603,43551063,374279864915,43800494,610862399010,44052908,991989935280,44302565,5893434651,44554559,17402645183,44803530,35943646365,45056959,65812656423,45303080,113930757179,45554672,191447608706,45802164,316324986992,46052911,517498787232,46302295,841583890229,46552064,3074679156,46802219,12861712571,47050518,28628336896,47300064,54027907086,47548215,94945871008,47799290,160863512855,48046434,267054904153,48295617,438126126427,48544071,713716857482,48796006,677744489,49048470,9000321026,49298905,22407748132,49549753,44006720594,49804517,78802032994,50056830,134856262534,50307721,225157985322,50557375,370631416795,50807120,604984856037,51058008,982521385632,51309070,5716565771,51557273,17117714543,51807775,35484631509,52058653,65073196930,52312523,112739509636,52565703,189528543838,52815751,313233429815,53064233,512518379370,53314024,833560598601,53564851,2924594555,53815963,12619930630,54060932,28238833269,54307539,53400428095,54556692,93935020704,54804435,159235062884,55056277,264431518838,55306940,433899929956,55556725,706908578398,55806245,549348706,56054526,8793479189,56301435,22074532063,56555312,43469919453,56809736,77937262116,57060177,133463142114,57311109,222913708970,57559659,367015953407,57810409,599160450170,58061101,973138438179,58312153,5540033707,58560779,16833326586,58811654,35026490825,59060167,64335145785,59311260,111550530977,59564033,187613134056,59811091,310147760736,60057167,507547457039,60307181,825552588218,60559018,2773399286,60809107,12376359574,61060772,27846447475,61310834,52768306127,61558121,92916690900,61808083,157594563185,62056275,261788721852,62304151,429642460847,62554179,700049920189,62803101,421224956,63053853,8587075577,63306242,21742021880,63560320,42934255289,63808749,77074322838,64057792,132072972200,64309047,220674185952,64560044,363408147688,64811970,593348380684,65062410,963775364331,65312875,5364465484,65562337,16550491283,65815713,34570851523,66066909,63601124093,66320731,110368043254,66572916,185708180982,66820844,307078936923,67074121,502603671476,67324080,817588294774,67574932,2624996273,67822386,12137286578,68077203,27461307851,68325128,52147857402,68576835,91917165969,68826620,155984357764,69074812,259194728147,69326263,425463613204,69578218,693317919294,69827973,295498034,70077203,8384533197,70325486,21415731952,70572324,42408611609,70822617,76227526294,71072153,130708807644,71322631,218476557046,71571243,359867831507,71819695,587645035156,72070163,954587441804,72320837,5192879414,72572033,16274071279,72819994,34125546861,73073858,62883751451,73325378,109212377002,73576656,183846436382,73825959,304079721068,74076617,497772022625,74324691,809804649437,74575254,2478502710,74823616,11901289737,75074286,27081123855,75326103,51535392117,75578103,90930502321,75830717,154394871503,76080479,256634112278,76330911,421338536015,76581009,686672540704,76831198,170920662,77082751,8183842713,77333614,21092425584,77586588,41887774596,77834246,75388473090,78083422,129357117443,78335444,216299023615,78588163,356359888735,78838699,581993842114,79089031,945483535102,79338979,5021923689,79587502,15998666485,79840466,33681877906,80089333,62169013635,80338919,108060955255,80589335,181991529706,80838247,301091520582,81086971,492958118998,81334821,802049592223,81585288,2333704426,81834258,11668023988,82082868,26705339517,82331992,50930014590,82577796,89955256932,82825602,152823779731,83075877,254103129517,83325426,417261196672,83574666,680104066151,83825214,47523507,84074594,7985053440,84322125,20772181826,84578689,41371871305,84827774,74557367833,85076566,128018231286,85326532,214142117131,85577765,352885175757,85828888,576396181355,86077885,936465867425,86326860,4853507682,86575097,15727353219,86824250,33244800104,87071796,61464894082,87320261,106926639410,87569836,180164180125,87818252,298147713933,88066475,488215732794,88316422,794409746597,88565277,2189460107,88816777,11435650672,89061257,26330992892,89312604,50326953208,89557866,88983742768,89807470,151258698876,90060816,251581830102,90309623,413199457023,90559357,673560722363,90807545,1092995098244,91057196,7787353159,91309233,20453692433,91554797,40858794180,91806159,73730815694,92059328,126686679919,92309182,211997026857,92557144,349429498174,92805710,570829185964,93053610,927497600735,93304351,4685264556,93558721,15456318572,93811916,32808171177,94066087,60761497812,94318013,105793488505,94568344,178338707094,94817773,295206930517,95067617,483478216754,95317730,786777746632,95568006,2047067599,95821928,11206260411,96069983,25961451963,96324826,49731633517,96578839,88024700000,96831429,149713708985,97082646,249092896558,97332930,409189858068,97581999,667101376255,97833613,1082589280689,98083970,7592625364,98337112,20139991649,98584271,40353431448,98835241,72916691179,99089614,125375149323,99338847,209884189289,99588123,346025778782,99838569,565345893787,100089173,918664177768,100339106,4518737141,100587587,15188047711,100834351,32375994660,101080652,60065274064,101330937,104671892500,101581032,176531848923,101828197,292296134838,102077739,478789010078,102327653,779223572048,102578452,1905541014,102827278,10978265333,103084620,25594158522,103331017,49139934610,103581260,87071490473,103831203,148178116403,104078916,246619101914,104328996,405204647340,104578790,660681317968,104830043,1072246754882,105080523,7398339343,105325041,19827002537,105576391,39849215066,105827505,72104413141,106075637,124066593104,106327037,207776143636,106578725,342629778882,106829714,559875037177,107076332,909850787951,107326010,4354683110,107578419,14923761581,107834706,31950237454,108087161,59379391623,108339828,103566955958,108592027,174751828494,108839071,289428573982,109088095,474169453648,109337483,771781602051,109590435,1765620916,109843063,10752858133,110081437,25231034137,110332245,48554951837,110584146,86129100354,110836098,146659953560,111084445,244173385931,111332609,401264670349,111582688,654334130404,111832392,1062021621551,112082235,7206698490,112330516,19518274761,112579315,39351863685,112826567,71303194772,113075874,122775853731,113327832,205696800289,113580176,339280017533,113829130,554478669836,114079358,901157398108,114328804,4191483496,114578149,14660851632,114824750,31526697331,115071718,58697080860,115320626,102467773271,115569496,172981077317,115821055,286575945643,116070241,469573952725,116320199,764378384800,116572061,1627574881,116823542,10530470029,117077203,24872773390,117331203,47977804257,117584728,85199332515,117837130,145162124809,118087024,241760427736,118336762,397377465370,118588257,648071956953,118839385,1051933443521,119089313,7017606287,119345815,19213652728,119593212,38861126452,119842768,70512631458,120091492,121502279413,120341045,203645109528,120589823,335974803789,120841856,549154066966,121090064,892579618993,121340784,4030509852,121591531,14401527806,121848303,31108934194,122096448,58024076648,122351076,101383583168,122603662,171234478752,122854083,283762226666,123105790,465041133865,123356015,757076146220,123604623,1490707061,123853727,10309979851,124099108,24517570166,124354613,47405582216,124603004,84277499491,124850892,143677078963,125100277,239368062129,125351142,393523435027,125599822,641863227150,125848234,1041931361613,126098295,6829284726,126351651,18910272345,126601495,38372389595,126848199,69725290790,127097434,120233896569,127347054,201601781662,127598937,332683062482,127847228,543851168197,128098749,884036804166,128349952,3869893989,128598478,14142780390,128848647,30692099632,129099926,57352568312,129355698,100301802920,129606264,169491762361,129854092,280954761586,130104565,460518389835,130356065,749790137907,130608500,1354154270,130856190,10089997457,131101704,24163185055,131349588,46834678258,131599110,83357789991,131850825,142195453631,132104529,236981207292,132355468,389678281232,132606643,635668796826,132855546,1031952315675,133105067,6642745718,133356961,18609763453,133613967,37888278558,133861319,68945402068,134112908,118977518757,134362414,199577793939,134614468,329422477452,134863343,538598461112,135114811,875574847099,135363607,3711222251,135611589,13887164859,135861937,30280310451,136107892,56689188084,136353678,99233116795,136605753,167770140307,136856191,278181278692,137105532,456050390108,137356298,742592321221,137604957,1218929695,137854252,9872154607,138104641,23812246615,138356744,46269326711,138612280,82447025204,138866602,140728238241,139114170,234617566255,139361816,385870524711,139611189,629534612689,139861486,1022070324749,140110603,6457527333,140368017,18311382009,140616828,37407594845,140865159,68171034631,141115404,117730035486,141367018,197568134878,141616540,326184975600,141866017,533382940567,142117990,867172795522,142366642,3554026557,142613775,13633927172,142858192,29872351977,143106656,56031978907,143361239,98174372077,143615170,166064533782,143866373,275433596512,144114854,451623954997,144363854,735461463758,144614439,1084565568,144864888,9655697881,145118771,23463541077,145367505,45707572329,145613726,81542055398,145865300,139270358519,146116601,232268964660,146366890,382086996623,146615821,623439459609,146864246,1012251211594,147114826,6273056551,147364597,18014204912,147616700,36928851212,147868062,67399792486,148117856,116487586891,148369137,195566586555,148619782,322960539867,148871301,528188468873,149119782,858804654230,149369972,3397755113,149619012,13382178561,149869593,29466792348,150119936,55378634377,150370541,97121853126,150621711,164368956454,150870664,272702071066,151122089,447223547051,151371539,728372535169,151619911,952250223,151869014,9442541797,152113038,23120152916,152364134,45154383935,152614526,80650885128,152866034,137834709208,153117303,229956175550,153365576,378361160925,153617158,617437247354,153867810,1002581823366,154118719,6092038169,154368255,17722589590,154618655,36459067453,154867186,66642984633,155117508,115268391639,155365693,193602498691,155615238,319796451817,155866648,523091215660,156115831,850593128525,156364982,3243839556,156613956,13134225026,156862972,29067346493,157108725,54735138728,157359007,96085200428,157608612,162698939179,157858566,270011722255,158110685,442889473878,158358673,721390470774,158607151,821609922,158859575,9232083997,159109836,22781111509,159359016,44608198160,159609211,79770995710,159858402,136417233148,160106697,227672663075,160356055,374682489219,160604579,611511015196,160854877,993034836731,161105359,5914110251,161355801,17435952907,161609777,35997304196,161859019,65899097615,162107537,114070011465,162356041,191671943332,162605677,316686383532,162854633,518080986662,163105695,842521796179,163355239,3092594895,163606181,12890574289,163857337,28674832371,164109508,54102809893,164360114,95066537244,164610470,161057902662,164860138,267368060404,165108247,438630611913,165358842,714529568823,165606553,693081380,165855934,9025028345,166105383,22447550903,166351004,44070841770,166604290,78905330400,166853238,135022671628,167104866,225426065639,167355018,371063286307,167605345,605680584986,167854307,983642184332,168104811,5737473816,168357735,17151396830,168604078,35538892630,168853433,65160610118,169099354,112880329827,169352796,189755401031,169602580,313598890214,169850933,513107125545,170101751,834509051377,170352228,2941349750,170601743,12646922818,170852087,28282316870,171099770,53470478977,171349653,94047870750,171601945,159416860828,171850431,264724390129,172099893,434371736558,172350792,707668644954,172599640,564219713,172849198,8817435949,173092341,22113125701,173341991,43532092696,173589383,78037421373,173837188,133624495703,174086057,223173644962,174334746,367434702789,174584382,599835043123,174835659,974225187667,175085228},
v2[] = {516914,0,7909327210,247996,20650189014,494199,41175344461,741867,74240768887,990884,127508199725,1238903,213320471137,1488494,351561528195,1737487,574263823815,1988067,933030702025,2238174,4787889955,2488178,15621644984,2738029,33074507269,2987804,61190557334,3237538,106484690902,3488423,179452214001,3739417,297000757453,3990955,486368019356,4239887,791433134353,4490336,2134746571,4741219,11347508705,4989280,26188998812,5235360,50098204813,5483077,88615235684,5734460,150665044668,5985470,250625470456,6236989,411658789573,6486750,671078752526,6735972,1088996717416,6985593,7712630908,7232311,20333317063,7480010,40664872959,7727096,73418414371,7978159,126183410525,8227743,211186274752,8478228,348123400096,8729657,568725099726,8978484,924107979538,9227690,4621442711,9477329,15353503397,9731057,32642538921,9983340,60494669081,10234342,105363635318,10483788,177646226292,10733584,294091364163,10984313,481681071951,11235903,783882599030,11486584,1992872518,11739534,11118953800,11988069,25820803537,12235285,49505053095,12483488,87659685761,12732026,149125681925,12980613,248145602142,13232393,407663794807,13484222,664642932551,13735325,1078628800049,13985929,7517398295,14234875,20018803006,14486321,40158200043,14734633,72602179030,14984746,124868479485,15236132,209067959091,15488054,344710855764,15740162,563227591537,15990883,915251654800,16240363,4454720767,16490935,15084919205,16740915,32209857666,16990461,59797632235,17238732,104240729349,17487179,175837257715,17736669,291177168779,17985729,476986388525,18234045,776319601703,18484929,1851116234,18739232,10890588601,18983359,25452913977,19238491,48912393781,19486606,86704928919,19736816,147587596515,19988258,245667791552,20237977,403672114127,20486894,658212452139,20738058,1068269484544,20988439,7323558986,21241853,19706533656,21493756,39655143309,21739486,71791769459,21986341,123562933314,22236912,206964762495,22485962,341322667685,22734908,557769319218,22985712,906458537962,23236334,4290068946,23486190,14819670024,23733799,31782549017,23984068,59109250487,24234704,103131766532,24482873,174050750915,24732595,288299158592,24980216,472349998385,25230239,768850512682,25480680,1710734844,25732830,10664438220,25977956,25088592230,26233754,48325482040,26484995,85759431184,26736033,146064427222,26986934,243214010432,27236166,399719144522,27486347,651844333881,27735508,1058010632332,27985816,7131768286,28227061,19397564493,28473383,39157403043,28719170,70989924483,28970702,122271184338,29221813,204883792787,29470272,337970286299,29720204,552368730897,29971111,897758348436,30221785,4127272583,30471029,14557409864,30725942,31360055575,30974429,58428625895,31224923,102035300196,31476082,172284375941,31726012,285453580169,31976722,467765854990,32227200,761465592132,32478701,1572244101,32726368,10441333753,32977441,24729177565,33229916,47746475595,33477509,84826668857,33724312,144561774556,33973523,240793280899,34223946,395819420123,34474043,645561992000,34721718,1047889963499,34971436,6941549589,35221287,19091127624,35469237,38663742215,35720017,70194651191,35971393,120990022403,36222418,202819878392,36472850,334645380582,36721997,547012405305,36971155,889129464543,37220888,3966062967,37473104,14297705839,37721023,30941680007,37964020,57754635134,38216726,100949520763,38464747,170535217078,38714167,282635736438,38964627,463226391189,39213242,754152648826,39463808,1435141335,39713175,10220465107,39962817,24373364596,40214488,47173271267,40465804,83903253379,40716502,143074179249,40969618,238396808471,41220843,391958773382,41468710,639342603202,41718529,1037870710119,41968071,6754455722,42220116,18789724876,42473235,38178191105,42725408,69412442670,42976456,119729907478,43222087,200789870231,43472031,331375096954,43720622,541744073754,43970901,880642336679,44220748,3806695412,44471423,14040969379,44720303,30528085091,44967154,57088345844,45217466,99876148217,45467671,168806045354,45717843,279850091360,45969157,458738798498,46219783,746923268357,46470867,1299624056,46720270,10002150769,46968419,24021666524,47215420,46606695936,47466890,82990517155,47717786,141603787729,47968990,236028050792,48219833,388142773853,48470292,633195139530,48719705,1027967326352,48968485,6568568230,49225848,18490265571,49469125,37695770909,49720320,68635277779,49973217,118477917594,50222972,198772951171,50470785,328125899423,50723617,536509711863,50975791,872209932999,51227427,3648674112,51478372,13786401761,51732492,30117984164,51979595,56427685242,52226710,98811843402,52478367,167091481333,52729674,277087978900,52980211,454289116243,53228990,739754960399,53478569,1165440526,53727855,9785985038,53976679,23673429866,54219259,46045696942,54465631,82086764167,54713917,140147868236,54964748,233682607223,55215419,384364333153,55466558,627108182487,55718281,1018161416409,55967759,6384840871,56221302,18194286218,56473994,37218956874,56724323,67867144325,56978323,117240476987,57230170,196779470429,57480471,324914460100,57729766,531336176853,57981488,863875519774,58232511,3492522697,58483865,13534846291,58735900,29712735640,58982896,55774841703,59230449,97760131531,59481940,165397204233,59733484,274358548202,59985790,449892083081,60235774,732671469307,60485452,1033047181,60737245,9572703304,60983033,23329839298,61238573,45492182566,61491780,81195068819,61741871,138711373191,61992159,231368455656,62240748,380636302745,62488510,621102434104,62737914,1008486331820,62987230,6202744986,63233879,17900935152,63490451,36746376966,63742085,67105832025,63993858,116014025156,64239428,194803692470,64488542,321731539797,64740620,526208585828,64989687,855615120181,65240987,3337248365,65495651,13284703872,65749857,29309763482,65998941,55125665244,66248018,96714327280,66494917,163712444225,66742001,271644449204,66991888,445519749157,67243062,725627766979,67493945,901223329,67745153,9360338837,67994781,22987726358,68239021,44941048652,68489535,80307208081,68741802,137281055555,68989529,229064255807,69237661,376924304261,69488749,615122513657,69738528,998852854893,69988721,6023036111,70235843,17611429352,70492835,36279991544,70742474,66354498813,70992570,114803649539,71243525,192853812778,71492247,318590340795,71742391,521148206276,71991765,847462997023,72243218,3184165505,72492412,13038091947,72739317,28912478890,72992901,54485651525,73238052,95683283946,73483871,162051463767,73734271,268968658210,73985351,441209128236,74233766,718683482800,74482916,770283483,74732618,9149398605,74980113,22647907766,75229783,44393610861,75482520,79425301849,75730979,135860330525,75978842,226775509306,76229246,373237200776,76477890,609182697658,76728163,989283985222,76979292,5843817868,77232715,17322714012,77482207,35814879649,77732013,65605217162,77982456,113596578595,78231876,190909256928,78485746,315457718244,78732310,516101642983,78982004,839333131372,79232546,3031826579,79482320,12792678317,79724105,28517124738,79977390,53848747466,80222737,94657250065,80473435,160398552997,80727389,266305867583,80976274,436919450454,81226490,711772937533,81474803,641471787,81726428,8941886748,81978724,22313612218,82227144,43855070484,82477936,78557729114,82727786,134462696085,82978737,224523961264,83227883,369610022577,83478632,603339420105,83730220,979870636290,83980153,5667028313,84230426,17037911196,84481313,35356070539,84732153,64866088952,84979857,112405864626,85231375,188991051429,85479344,312367545222,85728012,511123464485,85979131,831313431862,86228458,2882089052,86477342,12551455577,86728938,28128521923,86977153,53222719825,87225202,93648737970,87472621,158773869611,87719138,263688550111,87968704,432703028630,88217780,704980405206,88467802,513804751,88718382,8736218959,88965778,21982287521,89214526,43321316142,89465792,77697866526,89715249,133077482701,89965024,222292423080,90214364,366015079862,90463756,597548072341,90714907,970540944452,90964902,5491706374,91212482,16755472618,91460469,34901070380,91707335,64133097020,91954834,111225036221,92203097,187088771530,92453806,309303027988,92702392,506186617177,92952635,823360315351,93202815,2732148955,93452050,12309906422,93702256,27739393387,93953259,52595845096,94202865,92638861084,94453016,157146987459,94705165,261067690484,94955310,428480900665,95204464,698178680968,95454886,386594362,95704794,8531286681,95953806,21652147555,96201365,42789470238,96446547,76841078340,96698255,131697221936,96950480,220068863270,97201172,362432990132,97451514,591777430694,97700561,961244609992,97950051,5317813767,98197027,16475336819,98444297,34449779691,98693539,63406081084,98943426,110053834797,99192991,185202000365,99442494,306263494906,99693887,501290018134,99943309,815472037285,100192353,2584998549,100440481,12072851483,100695204,27357504749,100946907,51980633727,101197750,91647773651,101448206,155550374640,101699403,258495594184,101949879,424337328536,102199045,691503507226,102451263,261168273,102703017,8329228952,102951117,21326638527,103201407,42265084862,103449057,75996308882,103697353,130336323254,103946077,217876495336,104196010,358901149982,104449065,586087739359,104699885,952078683709,104950622,5145215224,105196742,16197285545,105449646,34001847301,105699548,62684474944,105949938,108891348489,106201543,183329268999,106452884,303246579542,106704396,496429856401,106953724,807642459234,107205252,2437605306,107456440,11835405275,107705353,26974985862,107955228,51364406978,108203059,90655050362,108453256,153951126527,108701821,255919252305,108951781,420186917249,109200293,684817316354,109449700,135846346,109700129,8127339003,109949506,21001399794,110200960,41741134761,110453697,75152240577,110701637,128976553719,110952530,215685946599,111202692,355372239702,111451659,580402768406,111701912,942920362141,111953253,4973848440,112206673,15921218739,112456722,33557111789,112703283,61968019211,112952956,107737159217,113201175,181469903817,113451333,300251196724,113699604,491604382050,113950295,799868761248,114201015,2292042163,114448879,11600907384,114696999,26597216665,114947746,50755831838,115200247,89674653706,115450173,152371736197,115697338,253374900556,115946742,416088041121,116194507,678214146697,116445579,11739875,116695478,7927407092,116943229,20679315220,117197048,41222265849,117449062,74316357893,117699996,127629971214,117951864,213516641449,118199901,351877552667,118450872,574772929833,118699858,933850856902,118950463,4804292720,119194749,15648069513,119436622,33117076391,119684351,61259135074,119933751,106595167567,120187118,179630188688,120434704,297287469422,120684875,486829904085,120936032,792177216992,121186485,2148119405,121435841,11369052011,121690241,26223704432,121938653,50154114587,122191351,88705304785,122441617,150810143622,122690662,250859220606,122939887,412035354528,123192139,671685387372,123443386,1089973989117,123693119,7730167930,123943725,20361568824,124196052,40710385794,124445107,73491734210,124689350,126301526553,124938593,211376556136,125188678,348429937754,125438856,569218923221,125686523,924903514838,125936056,4636126821,126184887,15377159015,126435075,32680647534,126686843,60556060841,126935771,105462535470,127187533,177805551563,127437334,294348032405,127687564,482094556929,127937001,784548711807,128185351,2005599411,128435284,11139456457,128685682,25853832695,128930763,49558262077,129179336,87745403812,129431004,149263771260,129679034,248368059991,129928754,408022167631,130178020,665220260799,130428927,1079558859150,130678496,7534905450,130925439,20047006573,131178493,40203635181,131430848,72675373647,131680268,124986393755,131933834,209257915661,132185473,345016870212,132433409,563720571414,132682837,916045830851,132932679,4470723398,133182790,15110698995,133438493,32251388145,133689138,59864536628,133941854,104348510375,134187147,176010889745,134436736,291456884887,134685266,477437002992,134935661,777045528192,135185378,1864707923,135436336,10912484398,135684505,25488187383,135935232,48969218185,136181200,86796471375,136432785,147735068831,136681979,245905365114,136933156,404054838277,137184345,658829009322,137435627,1069262740097,137685676,7341901090,137935377,19736082190,138183031,39702745048,138431195,71868454370,138682166,123686470303,138932679,207163776891,139183799,341643273736,139434828,558285806069,139684654,907290583233,139933367,4306386549,140189430,14845957116,140434453,31824896731,140686145,59177471364,140938922,103241668360,141187814,174227799642,141436998,288584378914,141687652,472809479978,141939623,769590724404,142192023,1725006630,142442563,10687429736,142693833,25125630989,142945377,48385150477,143192017,85855555365,143442508,146219280593,143694148,243463474648,143945070,400121024180,144194835,652491750128,144443398,1059053601000,144693543,7150796240,144943764,19428217889,145184454,39206784722,145430105,71069476824,145679100,122399340958,145929886,205090249304,146179598,338302881681,146430862,552904532582,146683711,898621508983,146932560,4143959402,147185668,14584291770,147438925,31403361528,147687933,58498390496,147944225,102147688854,148194056,172465430593,148445470,285745253760,148694950,468235732238,148945759,762222550822,149197269,1586958465,149447442,10465038090,149700409,24767364459,149947231,47807993511,150195129,84925772363,150445942,144721427381,150697356,241050477014,150949252,396233755521,151200660,646229474454,151449971,1048965258355,151699945,6962241045,151947685,19124461064,152203229,38717441350,152454008,70281159070,152705581,121129384100,152955296,203044385856,153205001,335007055655,153453409,547595052992,153703201,890068092939,153951799,3982974539,154200184,14324949956,154453499,30985569534,154705149,57825339904,154956614,101063424134,155204802,170718711897,155452606,282931341296,155704906,463702601926,155954347,754919810142,156205706,1449685643,156457374,10243895599,156715396,24411110374,156966123,47234078530,157212166,84001212107,157459766,143231987910,157707614,238651033496,157957524,392368322535,158207804,640002374908,158458560,1038933583063,158708851,6774496828,158959216,18822010522,159205874,38230202447,159455681,69496231279,159704619,119864888476,159955791,201007320609,160202591,331725403084,160453733,542308406999,160703528,881551460885,160953371,3824100021,161200752,14069007677,161455856,30573253943,161707657,57161111561,161956529,99993371782,162208301,168994889040,162456729,280154313151,162705716,459228891011,162957330,747712793006,163207879,1314350246,163454714,10025874297,163707311,24059884442,163955863,46668263948,164204979,83089701470,164449636,141763571075,164698929,236285457007,164949034,388557447993,165199223,633863167337,165447760,1029043499619,165698159,6588011679,165945381,18521588394,166194963,37746231166,166446082,68716567744,166696423,118608873376,166944045,198983917045,167193841,328465759158,167442655,537057216026,167691990,873091945912,167943723,3665659213,168196793,13813764182,168445794,30162064189,168697696,56498696937,168947646,98926241109,169196591,167275772773,169447646,277384867193,169697267,454767394585,169947165,740525452901,170197183,1179672547,170445905,9808912398,170690946,23710365188,170941373,46105198583,171189611,82182619533,171438541,140302288406,171690801,233931373479,171940203,384765088465,172191487,627753787394,172439594,1019201467225,172689134,6404557402,172943807,18226048963,173191945,37270125765,173441608,67949575946,173692620,117373271988,173944394,196993399269,174192381,325259093284,174443365,531891371075,174694249,864769921581,174944902,3509365518,175197090,13561979597,175447199,29756446529,175695663,55845258638,175944513,97873571123,176196298,165579951965,176445486,274652949422,176692084,450366354895,176943074,733435507028,177193284,1047294651,177441947,9595655526,177694724,23366814579,177940154,45551748646,178189648,81291027926,178436471,138865960515,178684358,231617491539,178933555,381037492174,179182798,621748738619,179432245,1009527509393,179682621,6222733463,179931970,17933135970,180179956,36798251540,180430007,67189400412,180678614,116148651505,180928131,195020571563,181178880,322080925679,181428393,526771436261,181680244,856521855649,181929806};
const int offset = 350125310,
T = 364258418,
a1 = 175147925,
a2 = 182058608;

const int B = 5e5;

inline LL nxt(LL x) {
    return (x + (x >> 20) + 12345) & mask;
}

inline int cnt(LL a, int n) {
    // dbg(a, n);
    int res = 0;
    for (int i=0; i<n; ++i) {
        res += ((a & 1) == 0);
        a = nxt(a);
    }
    // dbg(res);
    return res;
}

int main(int argc, char const *argv[]) {
    // code
    LL n;
    cin >> n;
    if (n < offset) {
        int id = n / B;
        // dbg(id);
        cout << v1[id * 2 + 1] + cnt(v1[id * 2], n % B) << endl;
    } else {
        int id = (n - offset) % T / B;
        cout << a1 + (n - offset) / T * a2 + + v2[id * 2 + 1] + cnt(v2[id * 2], (n - offset) % T % B) << endl;
    }
    

    return 0;
}
